/**
 * https://leetcode-cn.com/problems/invert-binary-tree/
 * 翻转二叉树
 * @param root 
 */
const invertTree = (root: TreeNode | null): TreeNode | null => {
    if (root === null) return null;

    // 模拟栈
    const stack: TreeNode[] = []


    // 循环只到栈为空
    while (stack.length > 0) {
        const n = stack.shift()!

        // 左右都为空, 啥都不用做
        if (n.left == null && n.right === null) continue

        // 交换左右子树
        const tmp = n.left;
        n.left = n.right;
        n.right = tmp

        // 左子树存在
        if (n.left !== null) stack.push(n.left)
        // 右子树存在
        if (n.right !== null) stack.push(n.right)
    }

    return root
};

// 递归
const invertTree2 = (root: TreeNode | null): TreeNode | null => {
    if (root === null) return null;

    // 翻转左子树
    let l: TreeNode | null = null
    if (root.left !== null) {
       l = invertTree(root.left)
    }

    // 翻转右子树
    let r: TreeNode | null = null    
    if (root.right !== null) {
        r = invertTree(root.right)
    }

    // 左右子树至少有一个存在, 才进行翻转
    if (l !== null || r !== null) {
        // 对该树进行翻转
        root.left = r;
        root.right = l
    }
    return root
};